In applicant's complementary application filed on even date herewith entitled “An Efficient Location Referencing Method”, a technique is described for producing a machine-readable representation of a location in a manner which not only is considered optimised as far as overall byte length is concerned, but which is also considered as being map-agnostic.
Any modern digital map (or mathematical graph, as they are sometimes known) of a road network, in its simplest form, is effectively a database consisting of a plurality of tables defining firstly nodes (which can be considered as points or zero-dimensional objects) most commonly representative of road intersections, and secondly lines between those nodes representing the roads between those intersections. In more detailed digital maps, lines may be divided into segments defined by a start node and end node, which may be the same in the case of a segment of zero length, but are more commonly separate. Nodes may be considered real or “valid” for the purposes of this application when they represent a road intersection at which a minimum of 3 lines or segments intersect, whereas “artificial” or “avoidable” nodes are those which are provided as anchors for segments not being defined at one or both ends by a real node. These artificial nodes are useful in digital maps to provide, among other things, shape information for a particular stretch of road or a means of identifying the position along a road at which some characteristic of that road changes, e.g. a speed limit.
In practically all modern digital maps, nodes and segments (and/or lines) are further defined by various attributes which are again represented by data in the tables of the database, e.g. each node will typically have latitude and longitude attributes to define its real-world position. The complete “graph” of the road network is described by millions of nodes and segments to cover an area of spanning one or more countries, or part thereof.
In the context of devising a means of efficiently referencing or describing a location (i.e. a path through a road network), it is not only highly inefficient simply to provide an ordered list of all nodes (and/or segments, and optionally their attributes) within the digital map which form part of the location, but such a referencing method would necessitate that exactly the same digital map was used during any de-referencing which later occurred, for example in a mobile device to which the location reference was transmitted, because nodes, segments, lines and their attributes are practically only ever uniquely defined in a particular version of a map created by a particular map vendor. Even fundamental attributes such as longitude and latitude for a particular node might differ between different digital maps.
One particular attribute often provided in digital maps is a Traffic Message Channel (TMC) location table reference. TMC is a technology for delivering traffic and travel information to vehicle users, and more particularly to navigation systems (either portable or integrated) present within those vehicles and which include some form of digital map. A TMC message consists of an event code (which need not be traffic-specific, although these are most common) and a location code, often consisting of an ordered list of location references by means of which the location of the traffic event can be determined in the digital map and thus represented graphically on the screen of the navigation system. A number of pre-defined nodes in most commercially available digital maps are assigned a TMC location reference which is determined with reference to a limited location table. The location table consists of 216 (65536) location references corresponding to a similar number of physical or real world locations, usually road intersections, also identifiable in the digital map.
Although TMC messages are very efficient in that they can be as short as 37 bits in length and therefore do not impinge significantly on available bandwidth for broadcast data, only a fixed number of location references are available, and therefore typically only motorways and major highways (or intersections thereon) in each country offering TMC can be referenced. There are various other disadvantages of TMC location references. For instance, TMC location tables are                often maintained through a public authority or National Government,        prone to change between update cycles, which are traditionally quite long,        non-existent, or available only commercially, in some markets.        
Of course, decoding a TMC location reference is intrinsically simple in that a simple queries can be performed in the digital map database for each TMC location code resulting in immediate identification of the relevant correct nodes and segments (each map provider will include TMC location codes as part of the map production process ensuring precision), and thus the location can be immediately resolved. However, as it is becoming possible to identify traffic build up on secondary and urban roads using GSM and GPS probe data (e.g. vehicles users increasingly possess either a mobile phone or a connected satellite navigation devices useful as probes), TMC location codes are simply inadequate as far resolution is concerned.
One attempt to overcome some of the limitations of TMC location references or map-specific references is the Dynamic Location Referencing project, also known as AGORA-C (in the process of standardization under no. ISO 17572-1, 2, and 3). Although a complete description of the AGORA-C location referencing approach is beyond the scope of this application, the fundamentals of the approach are that a location reference can be completely specified by a set of location points, specified by coordinate pairs of latitude and longitude and ordered in a list, each point complying with various rules but most importantly being consecutive in terms of the location being referenced and the previous point in the list, i.e. successive points form a next-point-relationship. As with other location referencing systems, each point is provided with a number of attributes which assist in better defining that point, but specific to the AGORA-C method is the identification of each point as one of a location point, an intersection point, a routing point, or some combination of these three. Each point along the location at which the road section signature changes is represented by an intersection point, so locations being paths over a road network and which pass through intersections without any road section signature change need not be referenced by an intersection point. For example, if a location includes a section of motorway which includes junctions that are not relevant as far as the location is concerned, then there is no need to include intersection points for such junctions. One of the earlier steps in the AGORA-C encoding method is the determination of all intervening intersection points between a first and a last intersection point along the location at which a change of road section signature occurs.
All these points are added to a table of points ultimately forming part of the AGORA-C location reference. Within this table, at least two routing points will also have been identified, again according to certain rules. Routing points are provided where an intersection points alone are insufficient to unambiguously determine the correct location in the decoder, and are either added as separate points, or where a required routing point coincides with existing intersection point, a simple attribute change on the latter is effected.
Although this referencing approach is comprehensive in that it is possible to accurately and repeatably encode and decode any location existing within a geographical information system, it is believed that that the system is excessive and possibly redundant in certain aspects, and a more efficient encoding and decoding system is possible. For instance, although the referencing method is independent of any pre-compilation work and is map-independent, the average AGORA-C message size is significantly higher than 30 bytes per location reference. In terms of the devices which might commonly decode location references, such as personal navigation devices, PDAs, mobiles, or in-car integrated navigation systems, it is desirable that the received message be as short as possible to enable rapid decoding and ultimate resolution of the location represented thereby.
It is therefore an object of this invention primarily to provide a method of resolving a location represented by structured data, typically a packet of binary data resulting from the encoding of an ordered list of location reference points representative of that location according to a physical data format specification, which is both economical in terms of required processing, and which nevertheless achieves very high success rates in terms of re-creating the correct location despite the relative brevity of received data regardless of the digital map used.